package com.LeeCode;

/**
 * 循环有序列表的插入
 */

public class CodeLCR029 {
    public static void main(String[] args) {

    }

    public Node insert(Node head, int insertVal) {
        Node newNode = new Node(insertVal);

        // 空链表
        if (head == null) {
            newNode.next = newNode;
            return newNode;
        }

        Node cur = head;

        while (true) {
            // 情况1: 插入值在当前节点和下一个节点之间
            if (cur.val <= insertVal && cur.next.val >= insertVal) {
                break;
            }

            // 情况2: 当前节点是链表的最大值，且插入值 >= 最大值 或 <= 最小值
            if (cur.next.val < cur.val) {
                // 插入值比最小值还小，或者比最大值还大
                if (insertVal >= cur.val || insertVal <= cur.next.val) {
                    break;
                }
            }

            // 情况3: 所有节点值相同，随便插入一个位置即可
            if (cur.next == head) {
                break;
            }

            cur = cur.next;
        }

        newNode.next = cur.next;
        cur.next = newNode;
        return head;
    }
}
